package study.datastructure.tree;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-11-28 11:17
 * <p>
 * 2024/11/28,
 * <p>
 * 2024/11/28,
 * <p>
 * 2024/11/28,
 * <p>
 * 2024/11/28,
 */

/**
 2024/11/28,
 */

import com.sun.org.apache.bcel.internal.generic.NEW;
import javafx.scene.Parent;
import jdk.internal.org.objectweb.asm.tree.ParameterNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 泛型key
 *  Comparable compareTo()的返回值
 * 一个负整数，零，或一个正整数，
 * 因为这个对象小于，等于，或大于指定的对象
 */
public class BSTTree2<K extends Comparable<K>, V> {

    /**
     * 泛型key 节点
     *
     * @param <K>
     */
    static class BSTNode<K, V> {
        K key;
        V val;  // 节点存储的值
        BSTNode<K, V> left;  // 左子节点
        BSTNode<K, V> right;  // 右子节点

        public BSTNode(K key) {
            this.key = key;
            this.left = null;
            this.right = null;
        }

        public BSTNode(K key, V value) {
            this.key = key;
            this.val = value;
        }

        public BSTNode(K key, V value, BSTNode<K, V> left, BSTNode<K, V> right) {
            this.key = key;
            this.val = value;
            this.left = left;
            this.right = right;
        }
    }

    BSTNode<K, V> root;

    public V get(K key) {
        BSTNode<K, V> p = root;
        while (p != null) {
            //key p.key
            int res = key.compareTo(p.key);
            if (res < 0) {
                p = p.left;
            } else if (res > 0) {
                p = p.right;
            } else {
                return p.val;
            }
        }
        //没找到
        return null;

    }
    //region 左右子树最大最小
    public V min() {
        if (root == null) {
            return null;
        }
        BSTNode<K, V> p = root;
        while (p.left != null) {
            p = p.left;
        }
        return p.val;
    }

    public V max() {
        if (root == null) {
            return null;
        }
        BSTNode<K, V> p = root;
        while (p.right != null) {
            p = p.right;
        }
        return p.val;
    }
    //endregion
    /**
     * 存储关键字和值
     *
     * @param key
     * @param val
     */
    public void put(K key, V val) {
        //区分
        //有值 覆盖

        BSTNode<K, V> p = root;
        BSTNode<K, V> parent = null;
        while (p != null) {
            //key p.key
            int res = key.compareTo(p.key);
            if (res < 0) {
                parent = p;
                p = p.left;
            } else if (res > 0) {
                parent = p;
                p = p.right;
            } else {
                //有值 覆盖
                p.val = val;
                return;
            }
        }

        //无值 新增

        BSTNode<K, V> node = new BSTNode<K, V>(key, val);
        if (parent == null) { //根节点为空
            root = node;
            return;
        }
        int res = parent.key.compareTo(key);
        if (res < 0) {
            parent.right = node;
        }else {
            parent.left = node;
        }
    }
    //region 前驱后继
    /**
     * 找到前驱节点
     * 思考： 记录找p的祖先节点 最近的 自左而来 方式不用栈更高效
     * 可以少一个循环 逻辑也简化了很多
     *
     * @param key
     * @return
     */
    public BSTNode<K, V> predecessor(K key) {
        BSTNode<K, V> p = root;
        //LinkedList<BSTNode<K,V>> stack=new LinkedList<>();
        BSTNode<K, V> ancestorFromLeft = null;
        while (p != null) {
            //stack.push(p);
            int res = key.compareTo(p.key);
            if (res < 0) {
                p = p.left;
            } else if (res > 0) {
                ancestorFromLeft = p;
                p = p.right;
            } else {
                break;
            }
        }
        //没找到
        if (p == null) {
            return null;
        }
        //找到节点p
        //p有左子树 -> 找左子树最大值
        if (p.left != null) {
            return max(p.left);
        }
        //p没有左子树 -> 找p的祖先节点 最近的 自左而来
        return ancestorFromLeft;

        /* BSTNode<K, V> pop = stack.pop();
        int res=key.compareTo(pop.key);
        while (pop != null&&res<0) {
            pop=stack.pop();
        }
        //期待res>0 key>pop.key
        return pop;*/
    }

    /**
     * 找到后驱节点
     *
     * @param key
     * @return
     */
    public BSTNode<K, V> successor(K key) {
        BSTNode<K, V> p = root;
        BSTNode<K, V> ancestorFromRight = null;
        while (p != null) {
            int res = key.compareTo(p.key);
            if (res < 0) {
                ancestorFromRight = p;
                p = p.left;
            } else if (res > 0) {
                p = p.right;
            } else {
                break;
            }
        }
        //没找到
        if (p == null) {
            return null;
        }
        //找到节点p
        //p有右子树 -> 找右子树最小值 找到后继节点
        if (p.right != null) {
            return min(p.right);
        }
        //p没有左子树 -> 找p的祖先节点 最近的 自左而来
        return ancestorFromRight;
    }

    /**
     * 找最大值
     *
     * @param node
     * @return
     */
    private BSTNode<K, V> max(BSTNode<K, V> node) {
        BSTNode<K, V> p = node;
        if (p == null) {
            return null;
        }
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }

    private BSTNode<K, V> min(BSTNode<K, V> node) {
        BSTNode<K, V> p = node;
        if (p == null) {
            return null;
        }
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }
    //endregion
    /**
     * 1.删除节点只有一个孩子 托孤给父节点
     * 2.删除节点没有孩子 托孤null
     * 3.删除节点有两个孩子 找到后驱节点 替换
     * leetcode450题 迭代法
     * 思考：重构托孤  方法中return 比外层的if else控制优雅的多
     * @param key 删除节点key
     * @return 被删除节点值
     */
    public V delete(K key) {
        BSTNode<K, V> p = root;
        BSTNode<K, V> parent = null;
        while (p != null&&!key.equals(p.key)) {
            int res = key.compareTo(p.key);
            parent = p;
            if (res < 0) {
                p = p.left;
            } else {
                p = p.right;
            }
        }
        //没找到
        if (p == null) {
            return null;
        }

        //找到节点p
        if (p.right == null) { //情况1 2
            // 托孤给父节点
            shift(parent, p, p.left);
        } else if (p.left == null) {//情况1
            // 托孤给父节点
            shift(parent, p, p.right);
        } else {
            //情况3
            BSTNode<K, V> s=p.right;
            BSTNode<K, V> sp=p;
            //找后驱节点
            while (s.left != null) {
                sp=s;
                s=s.left;
            }

            if (sp != p) { //s是p不相邻
                shift(sp, s, s.right);//不可能有左孩子
                s.right=p.right;
            }
            shift(parent, p, s);//相邻
            s.left=p.left;


        }

        return p.val;


    }

    //region 中序遍历 范围
    /**
     * 找小于key的节点
     * @param key
     * @return
     */
    public List<V> less(K key) {
        ArrayList<V> result = new ArrayList<>();
        BSTNode<K,V> p=root;
        LinkedList<BSTNode<K,V>> stack=new LinkedList<>();

        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p=p.left;
            } else {
                BSTNode<K, V> pop = stack.pop();
                //处理值
                if (pop.key.compareTo(key) < 0) {
                    result.add(pop.val);
                } else {
                    break;
                }
                p=pop.right;
            }

        }


        return result;
    }
    /**
     * 找大于key的节点
     * @param key
     * @return
     */
    public List<V> greater(K key) {
        ArrayList<V> result = new ArrayList<>();
        BSTNode<K,V> p=root;
        LinkedList<BSTNode<K,V>> stack=new LinkedList<>();

        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p=p.left;
            } else {
                BSTNode<K, V> pop = stack.pop();
                //处理值
                if (pop.key.compareTo(key) >0) {
                    result.add(pop.val);
                }
                p=pop.right;
            }

        }
        return result;
    }
    /**
     * 找大于key1的节点 小于key2的节点
     * @param key1
     * @param key2
     * @return
     */
    public List<V> between(K key1,K key2) {
        ArrayList<V> result = new ArrayList<>();
        BSTNode<K,V> p=root;
        LinkedList<BSTNode<K,V>> stack=new LinkedList<>();

        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p=p.left;
            } else {
                BSTNode<K, V> pop = stack.pop();
                //处理值
                if (pop.key.compareTo(key1) >= 0 && pop.key.compareTo(key2) <= 0) {
                    result.add(pop.val);
                } else if (pop.key.compareTo(key2) > 0) {
                    break;
                }
                p=pop.right;
            }

        }
        return result;
    }
    //endregion
    /**
     * 托孤
     * @param parent
     * @param p 被删节点
     * @param child
     */
    private void shift(BSTNode<K, V> parent, BSTNode<K, V> p, BSTNode<K, V> child) {
        if (parent == null) {
            root = child;
            return;
        }
        if (parent.left==p) {
            parent.left = child; // 继承
        } else {
            parent.right = child; //继承
        }
    }
}
